import sun.reflect.generics.tree.Tree;

/**
 * Created by L.jp
 * Description:给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 *
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 
 * User: 86189
 * Date: 2023-02-08
 * Time: 22:39
 */
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
public class Solution {
    //二叉树的最近公共祖先，这个和二叉搜索的最近公共祖先不一样，这个必须是全部节点搜索
    //方法就是先找到两个pq节点，然后根据两个pq节点的情况返回root,root就是任意一个根节点
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //终止条件
        if(root==null || root==p || root==q){ //也就包含了一种情况就是pq其中一个就是最近公共祖先
            return root;
        }
        //递归，递归每一层就是寻找pq节点，找到之后返回来
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);
        //第二种情况就是pq分布在root的两侧
        //如果left==null说明左边没有找到pq节点，那么就返回在右子树中的pq其中一个节点
        //如果right==null说明右边没有找到pq节点，那么就返回在左子树的pq其中一个节点
        //如果left!=null && right!=null 那么就说明找到了在左右子树找到了pq节点，返回root就是最近公共祖先，root可以是任意一个根节点
        return left==null ? right : (right==null ? left : root);
    }
}
